#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;
const ll N = 1000000007;

int waysToStep(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 2;

	vector<int> dp(n);
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 4;

	for (int i = 3; i < n; i++)
	{
		dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % N;
	}
	return dp[n - 1];
}

int waysToStep2(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;

	ll a = 1;
	ll b = 2;
	ll c = 4;
	ll d = 0;

	for (int i = 3; i < n; i++)
	{
		d = (a + b + c) % N;
		a = b;
		b = c;
		c = d;
	}
	return d;
}

int main()
{

	cout << waysToStep2(5) << endl;

	return 0;
}

class Solution {
public:
	int minCostClimbingStairs(vector<int>& cost) {
		int n = cost.size();
		vector<int> dp(n + 1);

		for (int i = 2; i <= n; i++) {
			dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
		}

		return dp[n];
	}
};

class Solution {
public:
	int numDecodings(string s) {
		int n = s.size();
		vector<int> dp(n);
		dp[0] = s[0] != '0';

		if (n == 1)
			return dp[0];

		if (s[0] != '0' && s[1] != '0')
			dp[1] += 1;
		int t = (s[0] - '0') * 10 + s[1] - '0';
		if (t >= 10 && t <= 26)
			dp[1] += 1;

		for (int i = 2; i < n; i++) {
			if (s[i] != '0')
				dp[i] += dp[i - 1];
			int t = (s[i - 1] - '0') * 10 + s[i] - '0';
			if (t >= 10 && t <= 26)
				dp[i] += dp[i - 2];
		}

		return dp[n - 1];
	}
};